/**
 * https://leetcode.cn/problems/house-robber-ii/submissions/566948107/
 * 213. 打家劫舍 II
 * medium 2024.09.22
 * 多维dp
 */

class Solution {
public:
    int fax(vector<int> nums,int l,int r){
        nums[l+1]=max(nums[l+1],nums[l]);
        for(int i=l+2;i<r;++i){
            nums[i]=max(nums[i-1],nums[i-2]+nums[i]);
        }
        return nums[r-1];
    }
    int rob(vector<int>& nums) {
        int n=nums.size();
        if(n<=3){
            for(int i=1;i<n;++i){
                if(nums[i]<nums[i-1])
                nums[i]=nums[i-1];
            }
            return nums[n-1];
        }
        return max(fax(nums,0,n-1),fax(nums,1,n));
    }
};